// https://leetcode.cn/problems/coin-change/

// 算法思路总结：
// 1. 动态规划解决零钱兑换问题（完全背包最小值）
// 2. 状态定义：dp[j]表示凑出金额j所需的最少硬币数
// 3. 状态转移：dp[j] = min(dp[j], dp[j-coin] + 1)
// 4. 初始化：dp[0]=0（金额0不需要硬币），其他为INF
// 5. 正序遍历允许硬币重复使用（完全背包）
// 6. 时间复杂度：O(n×amount)，空间复杂度：O(amount)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) 
    {
        int m = coins.size();

        vector<int> dp(amount + 1, INF);
        dp[0] = 0;

        for (int i = 1 ; i <= m; i++)
        {
            for (int j = 1 ; j <= amount ; j++)
            {
                if (j - coins[i - 1] >= 0 && dp[j - coins[i - 1]] != INF)
                {
                    dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
                }
            }
        }

        return dp[amount] == INF ? -1 : dp[amount];
    }
};

int main()
{
    vector<int> coins1 = {1, 2, 5}, coins2 = {2};
    int amount1 = 11, amount2 = 3;

    Solution sol;

    cout << sol.coinChange(coins1, amount1) << endl;
    cout << sol.coinChange(coins2, amount2) << endl;

    return 0;
}